Locator/Identifier Separation Protocol (“LISP”) has three different mechanisms through which an ingress tunnel router (“ITR”) can react to an egress tunnel router (“ETR”) failure, or “down,” event in a destination site, each of which has its own inherent limitations. The first such mechanism may be characterized as a routing monitor. In this mechanism, the ITR monitors remote routing locator (“RLOC”) advertisements in the underlay routing protocol. RLOCs are advertised as /32 or /128 host routes. This mechanism is non-functional in deployments involving multiple autonomous systems or service providers due to the fact that host routes may be aggregated or filtered. The second such mechanism may be characterized as remote RLOC probing. Using this mechanism, the ITR periodically probes every RLOC appearing in its map-cache. Probing a very large set of RLOCs can have scalability implications due to the fact that the frequency with which every RLOC can be probed is inversely proportional to the number of RLOCs being probed, eventually decreasing to the point where target convergence times cannot be met. The third such mechanism may be characterized as locator status bits (“LSB”). In this mechanism, each ETR in the destination site locally probes the RLOCs of the other ETRs in the same site. The ETR can then report to the ITR in the source site the status of all the RLOCs in the destination site on data packets flowing in the reverse direction using the locator status bitmap located in the LISP header. This mechanism is dependent on the implementation of bidirectional traffic and not all data planes support this mechanism. Additionally, there is no guarantee that the mechanism will work with bidirectional traffic if the underlying transport is UDP. Consider a situation in which reverse traffic includes only acknowledgements to individual data packets arriving through the ETR that is about to fail. Once the failure occurs, no more acknowledgements will be generated on which LSBs can be piggy-backed.